0001    //
0002    //  BigUInt Prime Test.swift
0003    //  BigInt
0004    //
0005    //  Created by Károly Lőrentey on 2016-01-04.
0006    //  Copyright © 2016 Károly Lőrentey. All rights reserved.
0007    //
0008    
0009    import Foundation
0010    
0011    /// The first several [prime numbers][primes]. 
0012    ///
0013    /// [primes]: https://oeis.org/A000040
0014    let primes
BigUInt Prime Test.swift:86
        for i in 1 ..< primes.count {
BigUInt Prime Test.swift:87
            let p = primes[i]
BigUInt Prime Test.swift:99
                guard isStrongProbablePrime(BigUInt(primes[i])) else {
: [BigUInt.Digit] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
0015    
0016    /// The ith element in this sequence is the smallest composite number that passes the strong probable prime test
0017    /// for all of the first (i+1) primes.
0018    ///
0019    /// This is sequence [A014233](http://oeis.org/A014233) on the [Online Encyclopaedia of Integer Sequences](http://oeis.org).
0020    let pseudoPrimes
BigUInt Prime Test.swift:97
        if self < pseudoPrimes.last! {
BigUInt Prime Test.swift:98
            for i in 0 ..< pseudoPrimes.count {
BigUInt Prime Test.swift:102
                if self < pseudoPrimes[i] {
: [BigUInt] = [
0021        /*  2 */ 2_047,
0022        /*  3 */ 1_373_653,
0023        /*  5 */ 25_326_001,
0024        /*  7 */ 3_215_031_751,
0025        /* 11 */ 2_152_302_898_747,
0026        /* 13 */ 3_474_749_660_383,
0027        /* 17 */ 341_550_071_728_321,
0028        /* 19 */ 341_550_071_728_321,
0029        /* 23 */ 3_825_123_056_546_413_051,
0030        /* 29 */ 3_825_123_056_546_413_051,
0031        /* 31 */ 3_825_123_056_546_413_051,
0032        /* 37 */ "318665857834031151167461",
0033        /* 41 */ "3317044064679887385961981",
0034    ]
0035    
0036    extension BigUInt {
0037        //MARK: Primality Testing
0038    
0039        /// Returns true iff this integer passes the [strong probable prime test][sppt] for the specified base.
0040        ///
0041        /// [sppt]: https://en.wikipedia.org/wiki/Probable_prime
0042        @warn_unused_result
0043        public func isStrongProbablePrime
BigUInt Prime Test.swift:99
                guard isStrongProbablePrime(BigUInt(primes[i])) else {
BigUInt Prime Test.swift:113
            guard isStrongProbablePrime(random) else {
(base: BigUInt) -> Bool {
0044            let dec = self - 1
0045    
0046            let r = dec.trailingZeroes
0047            let d = dec >> r
0048    
0049            var test = base.power(d, modulus: self)
0050            if test == 1 || test == dec { return true }
0051    
0052            if r > 0 {
0053                for _ in 1 ..< r {
0054                    test = (test * test) % self
0055                    if test == 1 {
0056                        return false
0057                    }
0058                    if test == dec { return true }
0059                }
0060            }
0061            return false
0062        }
0063    
0064        /// Returns true if this integer is probably prime. Returns false if this integer is definitely not prime.
0065        ///
0066        /// This function performs a probabilistic [Miller-Rabin Primality Test][mrpt], consisting of `rounds` iterations, 
0067        /// each calculating the strong probable prime test for a random base. The number of rounds is 10 by default,
0068        /// but you may specify your own choice.
0069        ///
0070        /// To speed things up, the function checks if `self` is divisible by the first few prime numbers before
0071        /// diving into (slower) Miller-Rabin testing.
0072        ///
0073        /// Also, when `self` is less than 82 bits wide, `isPrime` does a deterministic test that is guaranteed to 
0074        /// return a correct result.
0075        ///
0076        /// [mrpt]: https://en.wikipedia.org/wiki/Miller–Rabin_primality_test
0077        @warn_unused_result
0078        public func isPrime(rounds rounds: Int = 10) -> Bool {
0079            if count <= 1 && self[0] < 2 { return false }
0080            if count == 1 && self[0] < 4 { return true }
0081    
0082            // Even numbers above 2 aren't prime.
0083            if self[0] & 1 == 0 { return false }
0084    
0085            // Quickly check for small primes.
0086            for i in 1 ..< primes.count {
0087                let p = primes[i]
0088                if self.count == 1 && self[0] == p {
0089                    return true
0090                }
0091                if self.divideByDigit(p).mod == 0 {
0092                    return false
0093                }
0094            }
0095    
0096            /// Give an exact answer when we can.
0097            if self < pseudoPrimes.last! {
0098                for i in 0 ..< pseudoPrimes.count {
0099                    guard isStrongProbablePrime(BigUInt(primes[i])) else {
0100                        break
0101                    }
0102                    if self < pseudoPrimes[i] {
0103                        // `self` is below the lowest pseudoprime corresponding to the prime bases we tested. It's a prime!
0104                        return true
0105                    }
0106                }
0107                return false
0108            }
0109    
0110            /// Otherwise do as many rounds of random SPPT as required.
0111            for _ in 0 ..< rounds {
0112                let random = BigUInt.randomIntegerLessThan(self)
0113                guard isStrongProbablePrime(random) else {
0114                    return false
0115                }
0116            }
0117    
0118            // Well, it smells primey to me.
0119            return true
0120        }
0121    }